package com.autumn.algorithm;

import java.util.Arrays;

/**
 * 合并两个有序数组
 * 两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示nums1 和 nums2中的元素数目
 * 要求合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
 * 最终合并后的数组不由函数返回，要存储在数组 nums1中，nums1的初始长度为 m+n，m个元素表示应合并的元素，n个元素为0，应忽略，nums2 的长度为n
 * 例如：nums1 = [1,2,3,0,0,0]，m = 3，nums2 = [2,5,6].n = 3
 * 输出：[1,2,2,3,5,6]
 */
public class Algorithm04MergeTwoArrays {

    /**
     * 解法一：自带排序
     * 时间复杂度：O((m+n)log(m+n))
     */
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

    /**
     * 解法二：双指针，循环两个数组比较，小的值先存入临时数组
     * 时间复杂度O(m+n)
     * 空间复杂度O(m+n)
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        int[] temp = new int[k];
        for (int index = 0, nums1Index = 0, nums2Index = 0; index < k; index++) {
            if (nums1Index >= m) {
                //nums1数组若已取完，则完全取nums2数组的值
                temp[index] = nums2[nums2Index];
            } else if (nums2Index >= n) {
                //nums2数组若已取完，则完全取nums1数组的值
                temp[index] = nums1[nums1Index];
            } else if (nums1[nums1Index] < nums2[nums2Index]) {
                //nums1数组的元素值小于nums2数组，取nums1数组的值
                temp[index] = nums1[nums1Index];
            } else {
                //nums2数组的元素值小于nums1数组，取nums2数组的值
                temp[index] = nums2[nums2Index];
            }
            for (int i = 0; i < k; i++) {
                nums1[i] = temp[i];
            }
        }
    }

    /**
     * 解法三：双指针，不使用临时数组，两个数组倒遍历比较，大的值从nums1由后往前存入
     * 时间复杂度O(m+n)
     * 空间复杂度O(1)
     */
    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        for (int index = k - 1, nums1Index = m - 1, nums2Index = n - 1;
             index >= 0;
             index--) {
            if (nums1Index < 0) {
                //nums1数组若已取完，则完全取nums2数组的值
                nums1[index] = nums2[nums2Index--];
            } else if (nums2Index < 0) {
                //nums2数组若已取完，则完全取nums1数组的值
                break;
            } else if (nums1[nums1Index] > nums2[nums2Index]) {
                //nums1数组的元素值大于nums2数组，取nums1数组的值
                nums1[index] = nums1[nums1Index];
            } else {
                //nums2数组的元素值大于nums1数组，取nums2数组的值
                nums1[index] = nums2[nums1Index];
            }
        }
    }

}